/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 binary_find.h

	$Header: /resource_editor/binary_find.h $

	$NoKeywords: $

 ************************************************************************/

#if !defined(BINARY_FIND_H_INCLUDED)
#define BINARY_FIND_H_INCLUDED

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

// binary search which works on vectors and regular arrays
template <class t_iterator, class t_key>
t_iterator binary_find( t_iterator first, int size, t_key key_value )
{
	int mid;
	int upper = size;
	int lower = 0;

	while (true)
	{
		mid = (upper + lower) >> 1;
		if( upper <= lower )
			return first + mid;
		if (first[mid] < key_value )
			lower = mid + 1;
		else
			upper = mid;
	}
}
// binary search which works on vectors and regular arrays, given a key and a compare object

template <class t_iterator, class t_key, class t_compare>
t_iterator binary_find( t_iterator first, int size, t_key key_value, t_compare compare )
{
	int mid;
	int upper = size;
	int lower = 0;

	while (true)
	{
		mid = (upper + lower) >> 1;
		if( upper <= lower )
			return first + mid;
		if (compare( first[mid], key_value ))
			lower = mid + 1;
		else
			upper = mid;
	}
}

#endif